package com.learn.algorithm.dynamic.programming;

import java.util.Arrays;

public class LeetCode983 {
    public static int[] duration = {1, 7, 30};

    public static int mincostTickets(int[] days, int[] costs) {
        int[] dp = new int[days.length];
        Arrays.fill(dp, Integer.MAX_VALUE);
        return f2(days, costs, dp, 0);
    }

    public static int f1(int[] days, int[] costs, int i) {
        if (i == days.length) {
            return 0;
        }
        int ans = Integer.MAX_VALUE;
        for (int k = 0, j = i; k < duration.length; k++) {
            while (j < days.length && days[i] + duration[k] > days[j]) {
                j++;
            }
            ans = Math.min(ans, costs[k] + f1(days, costs, j));
        }
        return ans;
    }

    public static int f2(int[] days, int[] costs, int[] dp, int i) {
        if (i == days.length) {
            return 0;
        }
        if (dp[i] != Integer.MAX_VALUE) {
            return dp[i];
        }
        int ans = Integer.MAX_VALUE;
        for (int k = 0, j = i; k < duration.length; k++) {
            while (j < days.length && days[i] + duration[k] > days[j]) {
                j++;
            }
            ans = Math.min(ans, costs[k] + f2(days, costs, dp, j));
        }
        dp[i] = ans;
        return ans;
    }

    public static int mincostTickets2(int[] days, int[] costs) {
        int[] dp = new int[366];
        Arrays.fill(dp, Integer.MAX_VALUE);
        int n = days.length;
        dp[n] = 0;

        for (int i = n - 1; i >= 0; i--) {
            for (int k = 0, j = i; k < duration.length; k++) {
                while (j < days.length && days[i] + duration[k] > days[j]) {
                    j++;
                }
                dp[i] = Math.min(dp[i], costs[k] + dp[j]);
            }
        }
        return dp[0];
    }

    public static void main(String[] args) {
        System.out.println(mincostTickets2(new int[]{1, 4, 6, 7, 8, 20}, new int[]{2, 7, 15}));
    }
}
